#ifndef LIST_H_
#define LIST_H_

#include <cstdlib>
#include "mtm.h"

template<class T>
class Node {
	private:
	Node<T>* next;
	T data;

	public:
//	c'tors
	Node(const T& data, Node<T>* next): next(next),data(data){};
	Node(): next(NULL),data(0){};

	Node<T>* getNext(){
		return next;
	}

	T& getData(){
		return data;
	}

	bool isEnd() const{
		return next==NULL;
	}

	void setNext(Node<T>* node){
		this->next=node;
		return;
	}
};

template<class T>
class Iterator {
	private:
	Node<T>* ptr;
	public:

	Iterator(Node<T>* nodePtr): ptr(nodePtr){};

	Iterator<T>& operator++(){ //++i
		(*this)++;
		return *this;
	}

	Iterator<T> operator++(int){ //i++
		if(ptr->isEnd()){
			return *this;
		}
		Iterator<T> iterator(ptr);
		ptr=ptr->getNext();
		return iterator;
	}

	T& operator* () {
		if(ptr->isEnd()){
			throw ListExceptions::ElementNotFound();
		}
		return ptr->getData();
	}

	bool operator==(Iterator<T> iterator){
		return ptr==iterator.ptr;
	};

	bool operator!= (Iterator<T> iterator){
		return !((*this)==iterator);
	};

	template<class S> friend class List;
};

template<class T>
class List {
	private:
	Node<T>* head;
//	checks if the received iterator points to the list
	bool isIn(Iterator<T>& iterator) {
		if(iterator==end()){
			return true;
		}
		for(Iterator<T> searchIterator=begin();searchIterator!=end();
				searchIterator++){
			if(iterator==searchIterator){
				return true;
			}
		}
		return false;
	};
//	a recursive function for deleting the nodes in the list
	void listClear(Iterator<T> iterator){
		if(iterator==end()){
			delete(getNodePtr(iterator));
			return;
		}
		Iterator<T> copyIterator=iterator;
		listClear(++copyIterator);
		delete(getNodePtr(iterator));
		return;
	}

	static Node<T>& getNode(Iterator<T>& iterator){
		return *(iterator.ptr);
	}

	static Node<T>* getNodePtr(Iterator<T>& iterator){
		return iterator.ptr;
	}

	Node<T>& getPrevious(Iterator<T>& iterator){
		Iterator<T> previousIterator= begin();
		Iterator<T> searchIterator=begin();
		for(searchIterator++;previousIterator!=end();
				++searchIterator){
			if(searchIterator==iterator){
				return getNode(previousIterator);
			}
			previousIterator++;
		}
		return getNode(searchIterator);
	}

	void copyListData(const List<T>& list){
		head = new Node<T>;
		for (Node<T>*  toCopyNode = list.head; !(toCopyNode->isEnd());
				toCopyNode=toCopyNode->getNext()) {
			insert(toCopyNode->getData(),end());
		}
	}

	public:
	List():head(new Node<T>()){}

	List<T> (const List<T>& list){
		copyListData(list);
	}

	Iterator<T> begin(){
		Iterator<T> iterator(head);
		return iterator;
	}

	Iterator<T> end(){
		Iterator<T> iterator=begin();
		for(;!((getNode(iterator)).isEnd()); ++iterator);
		return iterator;
	}

	void insert (const T& data, Iterator<T> iterator){
		if(!isIn(iterator)){
			throw ListExceptions::ElementNotFound();
		}
		Node<T>* node = new Node<T>(data,getNodePtr(iterator));
		if(iterator==begin()){
			head = node;
		}
		else{
			getPrevious(iterator).setNext(node);
		}
		return;
	}

	void remove (Iterator<T> iterator){
		if(!isIn(iterator)){
			throw ListExceptions::ElementNotFound();
		}
		if((getNode(iterator)).isEnd()){
			throw ListExceptions::ElementNotFound();
		}
		Node<T>* nextPtr=(getNode(iterator)).getNext();
		if(iterator==begin()){
			head = nextPtr;
		}
		else{
			getPrevious(iterator).setNext(nextPtr);
		}
		delete(getNodePtr(iterator));
		return;
	}

	template <class Predicate>
	Iterator<T> find (const Predicate& predicate){
		for(Iterator<T> iterator=begin();iterator!=end();++iterator){
			if(predicate(*iterator)){
				return iterator;
			}
		}
		return end();
	}

	template <class Comapre>
	void sort (const Comapre& comparer){
		for(int counter=getSize();counter>0;--counter){
			Iterator<T> iterator=begin();
			Iterator<T> minIterator=begin();
			T min=*iterator;
			for(int i=1;i<=counter;++i){
				if(comparer(*iterator,min)==true){
					minIterator=iterator;
					min=*iterator;
				}
				iterator++;
			}
			remove(minIterator);
			insert(min,end());
		}
		return;
	}

	List<T>& operator= (const List<T>& list){
		if(this == &list){
			return *this;
		}
		listClear(begin());
		copyListData(list);
		return *this;
	}

	int getSize() {
		int counter = 0;
		for(Iterator<T> iterator=begin();iterator!=end();++iterator,counter++);
		return counter;
	}

	~List(){
		listClear(begin());
		return;
	}
};
#endif /* LIST_H_ */

